// #include<iostream>
// #include<vector>
// #include<algorithm>
// using namespace std;
// using ll  = long long;
// const int N = 2e5+9;
// ll a[N];
// ll stk[N],top;


// int main()
// {

//     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//     int n =0;
//     while(cin>>a[++n]);
//     n--;
//     ll ans = 0;
//     for(int i =1;i<=n;++i)
//     {
//         int pos = upper_bound(stk+1,stk+1+top,a[i],[](const int &u,const int &v)
//     {
//         return u>v;
//     }) - stk;
//     if(pos == top+1)top++;
//     stk[pos] = a[i];
//     ans = max(ans,top);
//     }
//     cout<<ans<<'\n';
    
//     top = 0,ans = 0;
//     for(int i = 1;i<=n;++i)
//     {
//         int pos= lower_bound(stk+1,stk+1+top,a[i])- stk;
//     if(pos == top+1)top++;
//     stk[pos] = a[i];
//     ans = max(ans,top);
//     }
//     cout<<ans<<'\n';





//     return 0;
// }
// #include<iostream>
// #include<algorithm>
// #include<vector>
// #include<queue>
// #include<stack>
// #include<unordered_map>


// using ll = long long;
// const int N = 1e7+3;
// using namespace std;
// ll fac[N],invfac[N];
// const ll p = 1e9 + 7;

// ll qmi(ll a, ll b)
// {
// 	ll res = 1;
// 	while (b)
// 	{
// 		if (b & 1)res = res * a % p;
// 		a = a * a % p, b >>= 1;
// 	}
// 	return res;
// }

// ll inv(ll x) {
// 	return qmi(x, p - 2);
// }

// ll C(ll n, ll m)
// {
// 	if (n < 0 || m < 0 || n < m)return 0;
// 	return fac[n] * invfac[n - m]%p * invfac[m]  % p;
// }

// void init(int n)
// {
// 	fac[0] = 1;
// 	for (int i = 1; i <= n; ++i)fac[i] = fac[i - 1] * i % p;
//     invfac[n] = inv(fac[n]);
//     for(int i = n-1;i>=0;--i)invfac[i] = invfac[i+1]*(i+1)%p;


// }


// void solve()
// {
// 	ll q,a,b,c,n,m;cin>>q>>a>>b>>c>>n>>m;
//     ll sum = 0;
//     for(int i = 1;i<=q;++i)
//     {

//     sum =(sum+C(n, m))%p ;
//         n = (n*a%c+b)%c,m = (m*b%c+a)%c;
//     }
//     cout<<sum <<'\n';

// }

// int main()
// {
// 	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
// 		init(1e7);

// 	int _ =1;
// 	while (_--)solve();
// 	return 0;
// }

//dp pathII
//线性
// #include<bits/stdc++.h>
// using ll = long long;
// using namespace std;

// const int N = 109;
// ll a[N],dp[N][N];
// const ll p = 1e6+7;

// int main()
// {
//     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//     ll m,n;cin>>n>>m;
//     for(int i= 1;i<=n;++i)cin>>a[i];
//     dp[0][0] = 1;
//     for(int i = 1;i<=n;++i)//到第i种花位置，可以i结尾（可能无i）
//     {
//         for(int j = 0;j<=m;++j)//共放了j盆花
//         {
//             for(int k = 0;k<=a[i]&&k<=j;++k)//最后有连续的k盆i花
//             {
//                 dp[i][j] = (dp[i][j]+dp[i-1][j-k])%p;
//             }
//         }
//     }
//     cout<<dp[n][m]<<'\n';




//     return 0;
// }

//区间dp
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
const int N = 509;
const ll inf = 4e18;
ll a[N],prefix[N],dp[N][N];
const ll p = 1e6+7;

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n;cin>>n;
    for(int i = 1;i<=n;++i)
    {
        cin>>a[i];
    }
    for(int i = 1;i<=n;++i)prefix[i] = prefix[i-1]+a[i];
    for(int len = 2;len<=n;++len)
    {   
        for(int i = 1,j = i + len - 1;j<=n;++i,++j){
        dp[i][j] = inf;
            for(int k  =i;k<j;++k)
            {
                dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+prefix[j]- prefix[i-1]);
            }
        }
}
cout<<dp[1][n]<<'\n'; 
    return 0;
}